#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;

/*
快速排序
原始递归版本
te...
*/
void QuickSort(vector<int> &v,int low,int high){
    if(low>=high){
        return ;
    }
    int i=low,j=high,k=v[i];
    while(i<j){
        while(i<j && v[j]>=k) j--;
        if(i<j) v[i++]=v[j];
        while(i<j && v[i]<=k) i++;
        if(i<j) v[j--]=v[i];
    }
    v[i]=k;
    QuickSort(v,low,i-1);
    QuickSort(v,i+1,high);
}
/*
随机优化快速排序
用中间值代替第一个值
*/
void QuickSort2(vector<int> &v,int l,int h){
    if(l>=h){
        return ;
    }
    int i=l,j=h,k=v[l+(h-l)/2];
    while(1){
        while(v[i]<k)i++;
        while(v[j]>k)j--;
        if(i<j)
            swap(v[i++],v[j--]);
        else
            break;
    }

    QuickSort2(v,l,j);
    QuickSort2(v,j+1,h);
}

/**
 * 普通快速排序，非递归版
 */
struct Range{
    int start,end;
    Range(int s=0,int e=0){start=s,end=e;}
};
void QuickSort3(vector<int> &v){
    int len=v.size();
    if(len<=0){
        return;
    }
    Range r[len+1];
    int p=0;
    r[p++]=Range(0,len-1);
    while(p){
        Range range=r[--p];
        if(range.start>=range.end) continue;
        int i=range.start,j=range.end,k=v[range.start];
        while(i<j){
            while(i<j && v[j]>=k) j--;
            if(i<j) v[i++]=v[j];
            while(i<j && v[i]<=k) i++;
            if(i<j) v[j--]=v[i];
        }
        v[i]=k;
        r[p++]=Range(range.start,i-1);
        r[p++]=Range(i+1,range.end);
    }
}

void QuickSort4(vector<int> &v){
    int len=v.size();
    if(len<=0){
        return;
    }
    Range r[len+1];
    int p=0;
    r[p++]=Range(0,len-1);
    while(p){
        Range range=r[--p];
        if(range.start>=range.end) continue;
        int i=range.start,j=range.end;
        int m=v[i+(j-i)/2];
        while(1){
            while(v[i]<m)i++;
            while(v[j]>m)j--;
            if(i<j){
                swap(v[i++],v[j++]);
            }else break;
        }

        r[p++]=Range(range.start,j);
        r[p++]=Range(j+1,range.end);
    }
}


int main(){
    vector<int> v={49 ,59 ,88 ,37 ,98 ,97 ,68 ,54 ,31,3};

    //QuickSort2(v,0,v.size()-1);
    QuickSort4(v);
    for(auto x:v){
        cout << x <<" ";
    }cout << endl;



    return 0;
}